// SPDX-License-Identifier: MPL-2.0
// (c) Hare authors <https://harelang.org>

use endian;
use hash;
use io;
use strings;

// The size, in bytes, of a CRC-64 checksum.
export def SZ: size = 8;

// ECMA polynomial for CRC-64. Used in ECMA-182 and xz-utils.
export def ECMA: u64 = 0xC96C5795D7870F42;

// ISO polynomial for CRC-64. Used in ISO 3309 (high-level data link controls).
export def ISO: u64 = 0xD800000000000000;

// Table of memoized values for each byte with the ECMA polynomial.
export const ecma_table: [256]u64 = [
	0x0000000000000000, 0xB32E4CBE03A75F6F, 0xF4843657A840A05B,
	0x47AA7AE9ABE7FF34, 0x7BD0C384FF8F5E33, 0xC8FE8F3AFC28015C,
	0x8F54F5D357CFFE68, 0x3C7AB96D5468A107, 0xF7A18709FF1EBC66,
	0x448FCBB7FCB9E309, 0x0325B15E575E1C3D, 0xB00BFDE054F94352,
	0x8C71448D0091E255, 0x3F5F08330336BD3A, 0x78F572DAA8D1420E,
	0xCBDB3E64AB761D61, 0x7D9BA13851336649, 0xCEB5ED8652943926,
	0x891F976FF973C612, 0x3A31DBD1FAD4997D, 0x064B62BCAEBC387A,
	0xB5652E02AD1B6715, 0xF2CF54EB06FC9821, 0x41E11855055BC74E,
	0x8A3A2631AE2DDA2F, 0x39146A8FAD8A8540, 0x7EBE1066066D7A74,
	0xCD905CD805CA251B, 0xF1EAE5B551A2841C, 0x42C4A90B5205DB73,
	0x056ED3E2F9E22447, 0xB6409F5CFA457B28, 0xFB374270A266CC92,
	0x48190ECEA1C193FD, 0x0FB374270A266CC9, 0xBC9D3899098133A6,
	0x80E781F45DE992A1, 0x33C9CD4A5E4ECDCE, 0x7463B7A3F5A932FA,
	0xC74DFB1DF60E6D95, 0x0C96C5795D7870F4, 0xBFB889C75EDF2F9B,
	0xF812F32EF538D0AF, 0x4B3CBF90F69F8FC0, 0x774606FDA2F72EC7,
	0xC4684A43A15071A8, 0x83C230AA0AB78E9C, 0x30EC7C140910D1F3,
	0x86ACE348F355AADB, 0x3582AFF6F0F2F5B4, 0x7228D51F5B150A80,
	0xC10699A158B255EF, 0xFD7C20CC0CDAF4E8, 0x4E526C720F7DAB87,
	0x09F8169BA49A54B3, 0xBAD65A25A73D0BDC, 0x710D64410C4B16BD,
	0xC22328FF0FEC49D2, 0x85895216A40BB6E6, 0x36A71EA8A7ACE989,
	0x0ADDA7C5F3C4488E, 0xB9F3EB7BF06317E1, 0xFE5991925B84E8D5,
	0x4D77DD2C5823B7BA, 0x64B62BCAEBC387A1, 0xD7986774E864D8CE,
	0x90321D9D438327FA, 0x231C512340247895, 0x1F66E84E144CD992,
	0xAC48A4F017EB86FD, 0xEBE2DE19BC0C79C9, 0x58CC92A7BFAB26A6,
	0x9317ACC314DD3BC7, 0x2039E07D177A64A8, 0x67939A94BC9D9B9C,
	0xD4BDD62ABF3AC4F3, 0xE8C76F47EB5265F4, 0x5BE923F9E8F53A9B,
	0x1C4359104312C5AF, 0xAF6D15AE40B59AC0, 0x192D8AF2BAF0E1E8,
	0xAA03C64CB957BE87, 0xEDA9BCA512B041B3, 0x5E87F01B11171EDC,
	0x62FD4976457FBFDB, 0xD1D305C846D8E0B4, 0x96797F21ED3F1F80,
	0x2557339FEE9840EF, 0xEE8C0DFB45EE5D8E, 0x5DA24145464902E1,
	0x1A083BACEDAEFDD5, 0xA9267712EE09A2BA, 0x955CCE7FBA6103BD,
	0x267282C1B9C65CD2, 0x61D8F8281221A3E6, 0xD2F6B4961186FC89,
	0x9F8169BA49A54B33, 0x2CAF25044A02145C, 0x6B055FEDE1E5EB68,
	0xD82B1353E242B407, 0xE451AA3EB62A1500, 0x577FE680B58D4A6F,
	0x10D59C691E6AB55B, 0xA3FBD0D71DCDEA34, 0x6820EEB3B6BBF755,
	0xDB0EA20DB51CA83A, 0x9CA4D8E41EFB570E, 0x2F8A945A1D5C0861,
	0x13F02D374934A966, 0xA0DE61894A93F609, 0xE7741B60E174093D,
	0x545A57DEE2D35652, 0xE21AC88218962D7A, 0x5134843C1B317215,
	0x169EFED5B0D68D21, 0xA5B0B26BB371D24E, 0x99CA0B06E7197349,
	0x2AE447B8E4BE2C26, 0x6D4E3D514F59D312, 0xDE6071EF4CFE8C7D,
	0x15BB4F8BE788911C, 0xA6950335E42FCE73, 0xE13F79DC4FC83147,
	0x521135624C6F6E28, 0x6E6B8C0F1807CF2F, 0xDD45C0B11BA09040,
	0x9AEFBA58B0476F74, 0x29C1F6E6B3E0301B, 0xC96C5795D7870F42,
	0x7A421B2BD420502D, 0x3DE861C27FC7AF19, 0x8EC62D7C7C60F076,
	0xB2BC941128085171, 0x0192D8AF2BAF0E1E, 0x4638A2468048F12A,
	0xF516EEF883EFAE45, 0x3ECDD09C2899B324, 0x8DE39C222B3EEC4B,
	0xCA49E6CB80D9137F, 0x7967AA75837E4C10, 0x451D1318D716ED17,
	0xF6335FA6D4B1B278, 0xB199254F7F564D4C, 0x02B769F17CF11223,
	0xB4F7F6AD86B4690B, 0x07D9BA1385133664, 0x4073C0FA2EF4C950,
	0xF35D8C442D53963F, 0xCF273529793B3738, 0x7C0979977A9C6857,
	0x3BA3037ED17B9763, 0x888D4FC0D2DCC80C, 0x435671A479AAD56D,
	0xF0783D1A7A0D8A02, 0xB7D247F3D1EA7536, 0x04FC0B4DD24D2A59,
	0x3886B22086258B5E, 0x8BA8FE9E8582D431, 0xCC0284772E652B05,
	0x7F2CC8C92DC2746A, 0x325B15E575E1C3D0, 0x8175595B76469CBF,
	0xC6DF23B2DDA1638B, 0x75F16F0CDE063CE4, 0x498BD6618A6E9DE3,
	0xFAA59ADF89C9C28C, 0xBD0FE036222E3DB8, 0x0E21AC88218962D7,
	0xC5FA92EC8AFF7FB6, 0x76D4DE52895820D9, 0x317EA4BB22BFDFED,
	0x8250E80521188082, 0xBE2A516875702185, 0x0D041DD676D77EEA,
	0x4AAE673FDD3081DE, 0xF9802B81DE97DEB1, 0x4FC0B4DD24D2A599,
	0xFCEEF8632775FAF6, 0xBB44828A8C9205C2, 0x086ACE348F355AAD,
	0x34107759DB5DFBAA, 0x873E3BE7D8FAA4C5, 0xC094410E731D5BF1,
	0x73BA0DB070BA049E, 0xB86133D4DBCC19FF, 0x0B4F7F6AD86B4690,
	0x4CE50583738CB9A4, 0xFFCB493D702BE6CB, 0xC3B1F050244347CC,
	0x709FBCEE27E418A3, 0x3735C6078C03E797, 0x841B8AB98FA4B8F8,
	0xADDA7C5F3C4488E3, 0x1EF430E13FE3D78C, 0x595E4A08940428B8,
	0xEA7006B697A377D7, 0xD60ABFDBC3CBD6D0, 0x6524F365C06C89BF,
	0x228E898C6B8B768B, 0x91A0C532682C29E4, 0x5A7BFB56C35A3485,
	0xE955B7E8C0FD6BEA, 0xAEFFCD016B1A94DE, 0x1DD181BF68BDCBB1,
	0x21AB38D23CD56AB6, 0x9285746C3F7235D9, 0xD52F0E859495CAED,
	0x6601423B97329582, 0xD041DD676D77EEAA, 0x636F91D96ED0B1C5,
	0x24C5EB30C5374EF1, 0x97EBA78EC690119E, 0xAB911EE392F8B099,
	0x18BF525D915FEFF6, 0x5F1528B43AB810C2, 0xEC3B640A391F4FAD,
	0x27E05A6E926952CC, 0x94CE16D091CE0DA3, 0xD3646C393A29F297,
	0x604A2087398EADF8, 0x5C3099EA6DE60CFF, 0xEF1ED5546E415390,
	0xA8B4AFBDC5A6ACA4, 0x1B9AE303C601F3CB, 0x56ED3E2F9E224471,
	0xE5C372919D851B1E, 0xA26908783662E42A, 0x114744C635C5BB45,
	0x2D3DFDAB61AD1A42, 0x9E13B115620A452D, 0xD9B9CBFCC9EDBA19,
	0x6A978742CA4AE576, 0xA14CB926613CF817, 0x1262F598629BA778,
	0x55C88F71C97C584C, 0xE6E6C3CFCADB0723, 0xDA9C7AA29EB3A624,
	0x69B2361C9D14F94B, 0x2E184CF536F3067F, 0x9D36004B35545910,
	0x2B769F17CF112238, 0x9858D3A9CCB67D57, 0xDFF2A94067518263,
	0x6CDCE5FE64F6DD0C, 0x50A65C93309E7C0B, 0xE388102D33392364,
	0xA4226AC498DEDC50, 0x170C267A9B79833F, 0xDCD7181E300F9E5E,
	0x6FF954A033A8C131, 0x28532E49984F3E05, 0x9B7D62F79BE8616A,
	0xA707DB9ACF80C06D, 0x14299724CC279F02, 0x5383EDCD67C06036,
	0xE0ADA17364673F59,
];

// Table of memoized values for each byte with the ISO polynomial.
export const iso_table: [256]u64 = [
	0x0000000000000000, 0x01B0000000000000, 0x0360000000000000,
	0x02D0000000000000, 0x06C0000000000000, 0x0770000000000000,
	0x05A0000000000000, 0x0410000000000000, 0x0D80000000000000,
	0x0C30000000000000, 0x0EE0000000000000, 0x0F50000000000000,
	0x0B40000000000000, 0x0AF0000000000000, 0x0820000000000000,
	0x0990000000000000, 0x1B00000000000000, 0x1AB0000000000000,
	0x1860000000000000, 0x19D0000000000000, 0x1DC0000000000000,
	0x1C70000000000000, 0x1EA0000000000000, 0x1F10000000000000,
	0x1680000000000000, 0x1730000000000000, 0x15E0000000000000,
	0x1450000000000000, 0x1040000000000000, 0x11F0000000000000,
	0x1320000000000000, 0x1290000000000000, 0x3600000000000000,
	0x37B0000000000000, 0x3560000000000000, 0x34D0000000000000,
	0x30C0000000000000, 0x3170000000000000, 0x33A0000000000000,
	0x3210000000000000, 0x3B80000000000000, 0x3A30000000000000,
	0x38E0000000000000, 0x3950000000000000, 0x3D40000000000000,
	0x3CF0000000000000, 0x3E20000000000000, 0x3F90000000000000,
	0x2D00000000000000, 0x2CB0000000000000, 0x2E60000000000000,
	0x2FD0000000000000, 0x2BC0000000000000, 0x2A70000000000000,
	0x28A0000000000000, 0x2910000000000000, 0x2080000000000000,
	0x2130000000000000, 0x23E0000000000000, 0x2250000000000000,
	0x2640000000000000, 0x27F0000000000000, 0x2520000000000000,
	0x2490000000000000, 0x6C00000000000000, 0x6DB0000000000000,
	0x6F60000000000000, 0x6ED0000000000000, 0x6AC0000000000000,
	0x6B70000000000000, 0x69A0000000000000, 0x6810000000000000,
	0x6180000000000000, 0x6030000000000000, 0x62E0000000000000,
	0x6350000000000000, 0x6740000000000000, 0x66F0000000000000,
	0x6420000000000000, 0x6590000000000000, 0x7700000000000000,
	0x76B0000000000000, 0x7460000000000000, 0x75D0000000000000,
	0x71C0000000000000, 0x7070000000000000, 0x72A0000000000000,
	0x7310000000000000, 0x7A80000000000000, 0x7B30000000000000,
	0x79E0000000000000, 0x7850000000000000, 0x7C40000000000000,
	0x7DF0000000000000, 0x7F20000000000000, 0x7E90000000000000,
	0x5A00000000000000, 0x5BB0000000000000, 0x5960000000000000,
	0x58D0000000000000, 0x5CC0000000000000, 0x5D70000000000000,
	0x5FA0000000000000, 0x5E10000000000000, 0x5780000000000000,
	0x5630000000000000, 0x54E0000000000000, 0x5550000000000000,
	0x5140000000000000, 0x50F0000000000000, 0x5220000000000000,
	0x5390000000000000, 0x4100000000000000, 0x40B0000000000000,
	0x4260000000000000, 0x43D0000000000000, 0x47C0000000000000,
	0x4670000000000000, 0x44A0000000000000, 0x4510000000000000,
	0x4C80000000000000, 0x4D30000000000000, 0x4FE0000000000000,
	0x4E50000000000000, 0x4A40000000000000, 0x4BF0000000000000,
	0x4920000000000000, 0x4890000000000000, 0xD800000000000000,
	0xD9B0000000000000, 0xDB60000000000000, 0xDAD0000000000000,
	0xDEC0000000000000, 0xDF70000000000000, 0xDDA0000000000000,
	0xDC10000000000000, 0xD580000000000000, 0xD430000000000000,
	0xD6E0000000000000, 0xD750000000000000, 0xD340000000000000,
	0xD2F0000000000000, 0xD020000000000000, 0xD190000000000000,
	0xC300000000000000, 0xC2B0000000000000, 0xC060000000000000,
	0xC1D0000000000000, 0xC5C0000000000000, 0xC470000000000000,
	0xC6A0000000000000, 0xC710000000000000, 0xCE80000000000000,
	0xCF30000000000000, 0xCDE0000000000000, 0xCC50000000000000,
	0xC840000000000000, 0xC9F0000000000000, 0xCB20000000000000,
	0xCA90000000000000, 0xEE00000000000000, 0xEFB0000000000000,
	0xED60000000000000, 0xECD0000000000000, 0xE8C0000000000000,
	0xE970000000000000, 0xEBA0000000000000, 0xEA10000000000000,
	0xE380000000000000, 0xE230000000000000, 0xE0E0000000000000,
	0xE150000000000000, 0xE540000000000000, 0xE4F0000000000000,
	0xE620000000000000, 0xE790000000000000, 0xF500000000000000,
	0xF4B0000000000000, 0xF660000000000000, 0xF7D0000000000000,
	0xF3C0000000000000, 0xF270000000000000, 0xF0A0000000000000,
	0xF110000000000000, 0xF880000000000000, 0xF930000000000000,
	0xFBE0000000000000, 0xFA50000000000000, 0xFE40000000000000,
	0xFFF0000000000000, 0xFD20000000000000, 0xFC90000000000000,
	0xB400000000000000, 0xB5B0000000000000, 0xB760000000000000,
	0xB6D0000000000000, 0xB2C0000000000000, 0xB370000000000000,
	0xB1A0000000000000, 0xB010000000000000, 0xB980000000000000,
	0xB830000000000000, 0xBAE0000000000000, 0xBB50000000000000,
	0xBF40000000000000, 0xBEF0000000000000, 0xBC20000000000000,
	0xBD90000000000000, 0xAF00000000000000, 0xAEB0000000000000,
	0xAC60000000000000, 0xADD0000000000000, 0xA9C0000000000000,
	0xA870000000000000, 0xAAA0000000000000, 0xAB10000000000000,
	0xA280000000000000, 0xA330000000000000, 0xA1E0000000000000,
	0xA050000000000000, 0xA440000000000000, 0xA5F0000000000000,
	0xA720000000000000, 0xA690000000000000, 0x8200000000000000,
	0x83B0000000000000, 0x8160000000000000, 0x80D0000000000000,
	0x84C0000000000000, 0x8570000000000000, 0x87A0000000000000,
	0x8610000000000000, 0x8F80000000000000, 0x8E30000000000000,
	0x8CE0000000000000, 0x8D50000000000000, 0x8940000000000000,
	0x88F0000000000000, 0x8A20000000000000, 0x8B90000000000000,
	0x9900000000000000, 0x98B0000000000000, 0x9A60000000000000,
	0x9BD0000000000000, 0x9FC0000000000000, 0x9E70000000000000,
	0x9CA0000000000000, 0x9D10000000000000, 0x9480000000000000,
	0x9530000000000000, 0x97E0000000000000, 0x9650000000000000,
	0x9240000000000000, 0x93F0000000000000, 0x9120000000000000,
	0x9090000000000000,
];

// Populate a user-provided buffer with the memoized values for a custom
// polynomial.
//
// The user-provided polynomial must be in the reversed form.
export fn memoize(polynomial: u64, buf: *[256]u64) void = {
	for (let i = 0z; i < 256; i += 1) {
		let value = i: u64;
		for (let z = 0z; z < 8; z += 1) {
			value = if (value & 0x1 == 1) {
				yield (value >> 1) ^ polynomial;
			} else {
				yield value >> 1;
			};
		};
		buf[i] = value;
	};
};

export type state = struct {
	hash::hash,
	table: *[256]u64,
	cval: u64,
};

const crc64_vtable: io::vtable = io::vtable {
	writer = &write,
	...
};

// Creates a [[hash::hash]] which computes the CRC-64 algorithm. This hash
// function does not allocate any state, so you do not need to call
// [[hash::close]] when you are done with it.
//
// It takes a table of memoized values for a given polynomail (for example,
// [[iso_table]] or [[ecma_table]]); a table for a custom polynomial, populated
// by [[memoize]] function, may also be used.
export fn crc64(table: *[256]u64) state = state {
	stream = &crc64_vtable,
	sum = &sum,
	reset = &reset,
	sz = SZ,
	table = table,
	cval = ~0u64,
	...
};

fn write(s: *io::stream, buf: const []u8) (size | io::error) = {
	let s = s: *state;
	for (let i = 0z; i < len(buf); i += 1) {
		let rightbits = s.cval & 0xFF;
		s.cval = s.table[rightbits ^ buf[i]] ^ (s.cval >> 8);
	};
	return len(buf);
};

fn reset(h: *hash::hash) void = {
	let h = h: *state;
	h.cval = ~0u64;
};

fn sum(h: *hash::hash, buf: []u8) void = {
	let h = h: *state;
	endian::host.putu64(buf, ~h.cval);
};

// Returns the 64-bit computed CRC.
export fn sum64(h: *hash::hash) u64 = {
	assert(h.reset == &reset);
	let h = h: *state;
	return ~h.cval;
};

@test fn crc64() void = {
	const vectors: [](str, u64, u64) = [
		("", 0, 0),
		("Man can believe the impossible, but can never believe the improbable. -- Oscar Wilde",
			0x17F71EF3BB851DC7, 0xD0E8ED57865D6AC6),
		("We learn from history that we do not learn from history. -- Georg Hegel",
			0xAA3C335BB49ABE9D, 0x5FD192CC516BBEC3),
		("The final delusion is the belief that one has lost all delusions. -- Maurice Chapelain",
			0x7DFC4F7CE9552D23, 0xF71B429C925D99AE),
	];

	let crc_ecma = crc64(&ecma_table);
	let crc_iso = crc64(&iso_table);

	let buf: [SZ]u8 = [0...];

	for (let i = 0z; i < len(vectors); i += 1) {
		let vec = vectors[i];

		hash::reset(&crc_ecma);
		hash::write(&crc_ecma, strings::toutf8(vec.0));
		hash::sum(&crc_ecma, buf);
		assert(endian::host.getu64(buf) == vec.1);
		assert(sum64(&crc_ecma) == vec.1);

		hash::reset(&crc_iso);
		hash::write(&crc_iso, strings::toutf8(vec.0));
		hash::sum(&crc_iso, buf);
		assert(endian::host.getu64(buf) == vec.2);
		assert(sum64(&crc_iso) == vec.2);
	};
};
